package _19_面试题;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

// 数字
public class _17_05_面试题字母与数字 {

    public static void main(String[] args) {

        _17_05_面试题字母与数字 v = new _17_05_面试题字母与数字();
      /*  String[] str = {
                "A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"
        };*/
        String[] str = {
                "A", "A"
        };
        System.out.println(Arrays.toString(v.findLongestSubarray(str)));
    }

    // 数组替代Hash表
    public String[] findLongestSubarray(String[] array) {
        int len = array.length;
        // 一号
        int[] map = new int[len << 1 + 1];
        Arrays.fill(map, -2);
        // 计算前缀和
        int newLen = 0, begin = 0, total = 0;
        map[total + len] = -1;
        for (int i = 0; i < array.length; i++) {
            char cur = array[i].charAt(0);
            // 将所有字母换成1，数字换成-1
            total += cur >= '0' && cur <= '9'? -1: 1;
            int prev = map[total + len];
            if (prev != -2) {
                if (i - prev > newLen) {
                    begin = prev + 1;
                    newLen = i - prev;
                }
            } else {
                map[total + len] = i;
            }
        }
        return Arrays.copyOfRange(array, begin, begin + newLen);
    }

    // Hash表存储数据
    public String[] findLongestSubarray1(String[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        // 计算前缀和
        int newLen = 0, begin = 0, total = 0;
        map.put(total, -1);
        for (int i = 0; i < array.length; i++) {
            // 将所有字母换成1，数字换成-1
            total += number(array[i])? -1: 1;
            Integer prev = map.get(total);
            if (prev != null) {
                if (i - prev > newLen) {
                    begin = prev + 1;
                    newLen = i - prev;
                }
            } else {
                map.put(total, i);
            }
        }
        return Arrays.copyOfRange(array, begin, begin + newLen);
    }

    public boolean number(String str) {
        char cur = str.charAt(0);
        return cur >= '0' && cur <= '9';
    }
}
